// 动态规划
function coinChange(coins, amount) {
  // 创建一个长度为 amount + 1 的数组 dp，用于存储凑成每个金额所需的最少硬币数
  // 初始值设为 Infinity，表示暂时无法凑出该金额
  const dp = new Array(amount + 1).fill(Infinity);
  // 凑成金额 0 所需的硬币数为 0
  dp[0] = 0;

  // 遍历从 1 到 amount 的每个金额
  for (let i = 1; i <= amount; i++) {
    // 遍历每个硬币面额
    for (let j = 0; j < coins.length; j++) {
      // 如果当前硬币面额小于等于当前要凑的金额
      if (coins[j] <= i) {
        // 更新 dp[i] 的值，取当前值和 dp[i - coins[j]] + 1 中的较小值
        // dp[i - coins[j]] + 1 表示使用当前硬币 coins[j] 后，凑成金额 i 所需的最少硬币数
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }

  // 如果 dp[amount] 仍然是 Infinity，说明无法凑出该金额，返回 -1
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 测试示例
const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount));
